namespace Calc
{
    public class Caculator
    {
        public double Eval(string text)
        {
            var tokens = Tokenize(text);
            var suffixTokens = InfixToSuffix(tokens);
            var result = CalcSuffix(suffixTokens);
            return result;
        }

        /// <summary>
        /// 将一个字符串分割成多个Token
        /// </summary>
        public List<Token> Tokenize(string text)
        {
            var tokens = new List<Token>();
            var chars = text.ToCharArray();

            // 遍历字符串中的每一个字符
            for(int i=0; i<chars.Length; i++)
            {
                var ch = chars[i];

                // 数字
                if(Char.IsDigit(ch))
                {
                    var numberText = "";

                    //是数字，并且没有超出最大长度，则继续匹配，直到不是数字为止
                    while (Char.IsDigit(ch))
                    {
                        numberText = numberText + ch;
                        i++;
                        if(i < chars.Length)
                        {
                            ch = chars[i];
                        }
                        else
                        {
                            break;
                        }
                        
                    }
                    //因为匹配到了不是数字的字符，所以这里退一步，这样在循环里面i递增后才能正确运行
                    i--;

                    // 将数字Token添加到tokens
                    var token = new NumberToken(numberText);
                    tokens.Add(token);
                }
                else if(ch == '+')
                {
                    tokens.Add(new AddToken());
                }
                else if(ch == '-')
                {
                    tokens.Add(new SubtractToken());
                }
                else if(ch == '*')
                {
                    tokens.Add(new MultipyToken());
                }
                else if(ch == '/')
                {
                    tokens.Add(new DivideToken());
                }
                else if(ch == '(')
                {
                    tokens.Add(new LeftParensToken());
                }
                else if(ch == ')')
                {
                    tokens.Add(new RightParensToken());
                }
                else
                {
                    throw new Exception($"未能识别的字符{ch}");
                }
                
            }
            return tokens;
        }

        /// <summary>
        /// 中缀转后缀
        /// </summary>
        /// <param name="tokens"></param>
        /// <returns></returns>
        /// <exception cref="Exception"></exception>
        public List<Token> InfixToSuffix(List<Token> tokens)
        {
            //运算符栈
            var S1 = new Stack<Token>();

            //操作数栈
            var S2 = new Stack<Token>();

            // 2 从左到右扫描
            foreach(var token in tokens)
            {
                // 3 遇到操作数，将其压入S2
                if(token is NumberToken)
                {
                    S2.Push(token);
                }
                // 4 遇到运算符，比较其与S1栈顶运算符的优先级
                else if(token is OperatorToken currentToken)
                {
                    while(S1.Count > 0)
                    {
                        // 4-1 如果S1为空，或者栈顶运算符为左括号，则直接将此运算符入栈
                        if (S1.Count == 0 || S1.Peek() is LeftParensToken)
                        {
                            S1.Push(token);
                            break;
                        }
                        // 4-2 否则，若优先级比栈顶运算符的高，也将运算符压入S1
                        else if (S1.Peek() is OperatorToken topToken && currentToken.Priority > topToken.Priority)
                        {
                            S1.Push(token);
                            break;
                        }
                        // 4-3 否则，将S1栈顶的运算符弹出并压入S2中，再次进入循环与S1中新的栈顶运算符比较
                        else
                        {
                            S2.Push(S1.Pop());
                        }
                    }
                    if(S1.Count == 0)
                    {
                        S1.Push(token);
                    }
                    
                }
                //5 遇到括号时
                else if(token is ParensToken)
                {
                    // 5-1，如果是左括号，直接压入S1
                    if(token is LeftParensToken)
                    {
                        S1.Push(token);
                    }
                    // 5-2，如果是右括号，依次弹出S1栈顶运算符，并压入S2，直到遇到左括号为止，此时将
                    // 这一对括号丢弃
                    else if(token is RightParensToken)
                    {
                        while(S1.Count > 0)
                        {
                            //是左括号，则丢弃，并终止循环
                            if(S1.Peek() is LeftParensToken)
                            {
                                S1.Pop();
                                break;
                            }
                            // 不是左括号就压入S2
                            else
                            {
                                S2.Push(S1.Pop());
                            }
                        }
                    }
                    // 既不是左括号，也不是右括号，则抛出异常
                    else
                    {
                        throw new Exception($"未能识别的Token");
                    }
                }
                // 不是操作数，运算符，括号，则抛出异常
                else
                {
                    throw new Exception($"未能识别的Token");
                }
            }
            // 7 将S1中剩余的运算符依次弹出并压入S2
            while(S1.Count > 0)
            {
                S2.Push(S1.Pop());
            }

            // 8 依次弹出S2中的元素并输出
            var tokensOfS2 = new List<Token>();
            while(S2.Count > 0)
            {
                tokensOfS2.Add(S2.Pop());
            }
            // 结果的逆序为后缀表达式
            var suffixTokens = new List<Token>();
            for(int i= tokensOfS2.Count-1; i>=0; i--)
            {
                suffixTokens.Add(tokensOfS2.ElementAt(i));
            }
            return suffixTokens;
        }

        public double CalcSuffix(List<Token> tokens)
        {
            var stack = new Stack<Token>();
            //遍历
            foreach(Token token in tokens)
            {
                // 如果是数字则入栈
                if(token is NumberToken)
                {
                    stack.Push(token);
                }
                // 如果是操作符，弹出栈顶元素，并计算结果，然后将结果入栈
                else if(token is OperatorToken)
                {
                    var b = (stack.Pop() as NumberToken).Number;
                    var a = (stack.Pop() as NumberToken).Number;
                    var value = Calc(a, b, token.Value);
                    stack.Push(new NumberToken(value.ToString()));
                }
                else
                {
                    throw new Exception("未能处理的token");
                }
            }
            //最终，栈里面就剩下一个元素，就是最终的结果
            if(stack.Count == 1 && stack.Peek() is NumberToken numberToken)
            {
                return numberToken.Number;
            }
            else
            {
                throw new Exception("未能正确处理表达式");
            }
        }

        private double Calc(double a, double b, string op)
        {
            if(op == "+")
            {
                return a + b;
            }
            else if(op == "-")
            {
                return a - b;
            }
            else if(op == "*")
            {
                return a * b;
            }
            else if(op == "/")
            {
                return a / b;
            }
            else
            {
                throw new Exception($"未能处理的运算符{op}");
            }
        }

        

    }
}